package com.wuxuan.algorithm_homework.sortTest;

import java.util.Arrays;

/**
 * 快速排序
 */
public class quickSort {

    public int[] quickSort(int[] q) {
        if (q == null || q.length == 0) {
            return q;
        }
        quickSort(q, 0, q.length - 1);
        return q;
    }

    private void quickSort(int[] q, int l, int r) {
        if (l >= r) {
            return;
        }

        //x 为基准
        //为了避免溢出
        int x = q[l + (r - l) / 2];
        int i = l;
        int j = r;
        while (i < j) {
            while (q[i] < x) {
                i++;
            }
            while (q[j] > x) {
                j--;
            }
            if (i < j) {
                swap(q, i, j);
            }
        }
        quickSort(q, l, j);
        quickSort(q, j + 1, r);
    }

    /**
     * 这里 a 和 b 是按值传递的，因此你在方法中对 a 和 b 的修改不会影响到原始数组中的值。a 和 b 只是数组中元素的副本，而不是数组的引用!!!!!!!
     * @param a
     * @param b
     */
    private void swap(int a, int b) {
        int temp = a;
        a = b;
        b = temp;
    }

    /**
     * q 是数组的引用，因此你可以直接通过索引访问和修改数组中的值。
     * i 和 j 是数组中的索引，它们也是按值传递的，但你只需要它们的值来访问数组中的元素。
     * @param q
     * @param i
     * @param j
     */
    private void swap(int[] q, int i, int j) {
        int temp = q[i];
        q[i] = q[j];
        q[j] = temp;
    }

    public static void main(String[] args) {
        quickSort qs = new quickSort();

        int[] q = {5, 3, 4, 1, 9, 8, 7, 6};

        System.out.println(Arrays.toString(q));

        int[] result = qs.quickSort(q);

        System.out.println(Arrays.toString(result));
    }

}
